1. Field of the Invention
The present invention relates to apparatus and methods for the coding and storing of graphical information. More particularly, the present invention relates to apparatus and methods for generating and storing coded representations of high fidelity multilevel graphic art images suitable for the photocomposition of printed materials. Because of the ease of generating efficient codes using the present invention, applications including real time facsimile and teleconferencing transmission, long term storage of x-ray or like data, and machine cutting operations are possible.
2. Description of the Prior Art
Recent years have witnessed greatly increased usage of automatic means for composing and printing page copy for use in directories, catalogs, magazines and other printed works. An important aspect of such photocomposition schemes is the coding and storage of machine-compatible signals representative of graphical source information. In particular, when pictorial information and/or high-resolution type fonts are to be used, it has been found necessary to identify by scanning with great particularity the individual graphical entities associated with the source material. To permit the further processing of these data it has usually been necessary to store them in memories having substantial capacity. Often these data are stored for long times, as when they are to be used in successive issues of a book, magazine or the like. Because typical published materials, especially photographic or other picture materials are so diverse, and because the information content of such materials is so great, the volume of data required to be stored is potentially very large. It is especially important therefore that these data be stored in as efficient a manner as possible.
A number of particular coding and storage schemes have been developed for efficiently storing and transmitting information. For example, the variable length codes described in Elias, "Predictive Coding", IRE Transactions Information Theory, March 1955, have proved to be useful in many variations. The well-known Huffman codes described, for example, in Huffman, "A Method for the Construction of Minimum Redundancy Codes," Proceedings I.R.E., September 1952, pp. 1098-1101, and Fano, Transmission of Information, The MIT Press, 1961, pp. 75-81, offer optimum efficiency under particular circumstances. The application of these techniques to graphical information has generally been limited to one-dimensional coding, i.e., coding of signals associated with a single scan line in the source copy.
U.S. Pat. No. 3,461,231 issued Aug. 12, 1969 to R. V. Quinlan describes a system for performing limited two-dimensional encoding. However, his techniques are limited to transmitting only an indication of the differences between data corresponding to two successive scan lines. A related technique is presented in Tyler, "Two Hardcopy Terminals for PCM Communications of Meterological Products," Conference Record, 1969 International Conference on Communications, June 9-11, 1969, pp. 11-21 through 11-28. Tyler encodes his data (meteorological information) in terms of differential lengths for run lengths on two successive scan lines. Huang, "Run-Length Coding and its Extensions," in Huang and Tretiak (Eds.), Picture Bandwidth Compression, Gordan and Breach, New York 1972, pp. 231-264, discusses some extensions to the work of Tyler.
Other two-dimensional coding of picture information is described in D. N. Grahan, "Image Transmission by Two-Dimensional Contour Coding," Proceedings of the IEEE, Vol. 55, No. 3, March 1967, pp. 336-345.
The above-cited Quinlan and Tyler references indicate a need to determine not only what is encoded, i.e., which parameters are encoded, but also how, exactly, these parameters are to be encoded. The latter aspect of the problem is also treated in U.S. Pat. No. 3,643,019, issued Feb. 15, 1972 to J. P. Beltz. Particular reference is made by Beltz of the applicability of his techniques in commercial photocomposition systems such as the RCA VIDEOCOMP Series 70/800. Although Beltz applies a variable-length coding to segments defining a "zone", each such zone is the area defined by a single scan line, i.e., he does not attempt to extend his results to two-dimensional coding. Likewise, though Graham and Huang speak of Huffman codes, their application is to very specific geometric entities.
The present invention, while related, in part, to earlier work described in my copending U.S. patent applications, Ser. Nos. 425,506 and 675,926 filed Dec. 17, 1973 and Apr. 12, 1976, provides for the first time a method and apparatus for coding multi-level images. My application Ser. No. 425,506 discloses an approach to the efficient coding of the "blobs" of one of two levels. This approach extends with important differences to the efficient coding of regions of images having more than two gray levels or colors or textures. It also realizes many of the processing simplifications described in my application Ser. No. 675,926.